#include <vector>

using std::vector;

// 版本1 [left,right] 左闭右闭
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // [left,right] 左闭右闭
        while(left <= right) // 因为[left,right] 左闭右闭，所以这里要用等于符号
        {
            int middle = (left + right) >> 1;
            if(nums[middle] == target) return middle;
            else if(nums[middle] > target) // 在左边
            {   
                right = middle - 1;
            }
            else if (nums[middle] < target) // 在右边
            {
                left = middle + 1;
            }
        }
        return -1;
    }
};

// 版本2 [left,right) 左闭右开
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // [left,right) 左闭右闭
        while(left < right) // 因为[left,right) 左闭右闭，所以这里不要用等于符号
        {
            int middle = (left + right) >> 1;
            if(nums[middle] == target) return middle;
            else if(nums[middle] > target) // 在左边
            {   
                right = middle;
            }
            else if (nums[middle] < target) // 在右边
            {
                left = middle + 1;
            }
        }
        return -1;
    }
};
